/*
 * @lc app=leetcode.cn id=909 lang=typescript
 *
 * [909] 蛇梯棋
 */

// @lc code=start

class Data {
  constructor(public positon: number, public step: number) {
    this.positon = positon;
    this.step = step;
  }
}

function snakesAndLadders(board: number[][]): number {
  const n = board.length;
  const getCoordinates = (position: number): number[] => {
    // 这里格子的下标是从1开始计算的，计算坐标的时候要减去1
    let r = ((position - 1) / n) >> 0;
    let c = (position - 1) % n;
    // 奇数行，从右往左排列
    if (r % 2 === 1) {
      c = n - 1 - c;
    }
    return [n - 1 - r, c];
  };
  // 已访问状态
  const visited: number[] = new Array(n * n + 1).fill(0);
  // 搜索状态
  const queue: Data[] = [];
  // 初始化从位置1开始搜索
  queue.push(new Data(1, 0));
  visited[1] = 1;

  while (queue.length) {
    const data = queue.shift();
    if (data.positon === n * n) return data.step;
    for (let i = 1; i <= 6; i++) {
      let next = data.positon + i;
      if (next > n * n) break;
      // 一维坐标转二维坐标
      let [x, y] = getCoordinates(next);
      // 是否有蛇或者梯子
      if (board[x][y] > 0) next = board[x][y];
      if (visited[next] === 1) continue;
      visited[next] = 1;
      queue.push(new Data(next, data.step + 1));
    }
  }

  return -1;
}
// @lc code=end
